#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
算法导论, 动态规划, 最后一个示例. page213
"""

from pprint import pprint


class Solution:
    def __init__(self, keys, not_matchs):
        self.keys = keys
        self.not_matchs = not_matchs
        self.len_keys = len(self.keys)
        self.len = len(keys) + len(not_matchs)

        self.init()
        # print(self.prob)
        # self.calc()

    def init(self):
        self.prob = self.len * [0]
        self.prob[0] = self.not_matchs[0][1]

        till = 0

        # key 都在奇数位置
        for idx in range(self.len_keys):
            till += 1
            self.prob[till] = self.keys[idx][1]
            till += 1
            self.prob[till] = self.not_matchs[idx+1][1]

    def calc(self):
        self.memory = {}
        res = self.calc_range_rec(0, self.len)
        self.print_tree(0, self.len, 0)
        return res

    def print_tree(self, start, end, depth):
        if end - start == 1:
            return

        # print(depth * "    ", start, "-", end)
        prob, root = self.memory[(start, end)]

        # print(depth * "    ", start, "-", end)
        # NOTE: 和<算法导论>p213 b图一致
        print(depth * "    ", self.keys[self.mid2real(root)-1][0], ":", prob, sep="")

        if end - start == 3:
            return

        self.print_tree(start, root, depth+1)
        self.print_tree(root+1, end, depth+1)

    def calc_range_rec(self, start_idx, end_idx):
        # [start_idx, end_idx), 开闭区间
        assert start_idx % 2 == 0       # not_matchs

        key = start_idx, end_idx
        res = self.memory.get(key)

        if res is not None:
            return res

        if end_idx - start_idx == 1:
            return self.prob[start_idx], None

        min_value = 9999999999999
        min_root = None
        for root_idx in range(start_idx+1, end_idx, 2):
            part1 = self.calc_range_rec(start_idx, root_idx)[0]
            part2 = self.calc_range_rec(root_idx+1, end_idx)[0]
            part3 = sum(self.prob[start_idx:end_idx])      # 所有节点都因为root插入, 而下降一级(概率总和上升)

            search_sum = part1 + part2 + part3

            if search_sum < min_value:
                min_value = search_sum
                min_root = root_idx

        # self.memory[key] = min_value, (min_root+1) // 2
        self.memory[key] = min_value, min_root
        # return min_value, min_root
        return self.memory[key]

    def mid2real(self, n):
        # 把prob中key索引, 转换为真正的key索引
        return (n+1) // 2


def test():
    # ------------------- case1 ---------------------
    keys      = [
        ("k1", 0.15),
        ("k2", 0.1),
        ("k3", 0.05),
        ("k4", 0.1),
        ("k5", 0.2)
    ]

    not_matchs = [
        ("_k1",   0.05),
        ("k1_k2", 0.1),
        ("k2_k3", 0.05),
        ("k3_k4", 0.05),
        ("k4_k5", 0.05),
        ("k5_",   0.1),
    ]
    assert len(not_matchs) == len(keys) + 1


    s = Solution(keys, not_matchs)
    assert sum(s.prob) - 1 < 0.00000001

    def mid2real(n):
        return (n+1) // 2

    s.calc()
    print('-------------------  ---------------------')

    # ------------------- case2: page217 15.5-2习题 ---------------------
    keys      = [
        ("k1", 0.04),
        ("k2", 0.06),
        ("k3", 0.08),
        ("k4", 0.02),
        ("k5", 0.10),
        ("k6", 0.12),
        ("k7", 0.14),
    ]

    not_matchs = [
        ("  _k1",   0.06),
        ("k1_k2", 0.06),
        ("k2_k3", 0.06),
        ("k3_k4", 0.06),
        ("k4_k5", 0.05),
        ("k5_k6", 0.05),
        ("k6_k7", 0.05),
        ("k7_",   0.05),
    ]
    assert len(not_matchs) == len(keys) + 1


    s = Solution(keys, not_matchs)
    assert sum(s.prob) - 1 < 0.00000001
    s.calc()


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
